//动态规划
//[0,1,1,3,2,3]
//[1,1,1,1,1,1] 初始化一个数组
var maxChildren = function(nums){
    let n = nums.length
    if(n == 0 ) return 0
    let dp = Array(n).fill(1)
    for(let i=0;i<n;i++){
        for(let j=0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i] = Math.max(dp[i],dp[j]+1)
            }
        }  
    }
    return Math.max(...dp)
}
let nums = [0,1,1,3,2,3]
maxChildren(nums)
//贪心+二分  只是求出了最长的子序列的长度
//诡异的走法，比如现在的子序列为[1,4,5] 下一个元素为3，那么我们就找到大于3的第一个位置把他替换所以子序列为[1,3,5]
var maxChildren1 = function(nums){
    let n = nums.length
    if(n==0){
        return 0
    }
    let arr = [nums[0]]
    for(let i=0;i<n;i++){
        if(nums[i]>arr[arr.length-1]){//当前值比数组最后一个大，直接push进去
            arr.push(nums[i])
        }else{//如果比他小就找到对应的位置替换，二分查找
            let left = 0
            let right = arr.length - 1
            while(left<right){
                let mid = (left+right) >> 1
                if(arr[mid]<nums[i]){//如果中间值比当前值小
                    left = mid + 1
                }else {
                    right  = mid
                }
            }
            arr[left] = nums[i]
        }
    }
    return arr.length
}